| 翻訳と辞書 |
| Fleischner's theorem ： ウィキペディア英語版 |
Fleischner's theorem
In graph theory, a branch of mathematics, Fleischner's theorem gives a sufficient condition for a graph to contain a Hamiltonian cycle. It states that, if ''G'' is a 2-vertex-connected graph, then the square of ''G'' is Hamiltonian. it is named after Herbert Fleischner, who published its proof in 1974.
==Definitions and statement==
An undirected graph ''G'' is Hamiltonian if it contains a cycle that touches each of its vertices exactly once. It is 2-vertex-connected if it does not have an articulation vertex, a vertex whose deletion would leave the remaining graph disconnected. Not every 2-vertex-connected graph is Hamiltonian; counterexamples include the Petersen graph and the complete bipartite graph ''K''2,3.
The square of ''G'' is a graph ''G''2 that has the same vertex set as ''G'', and in which two vertices are adjacent if and only if they have distance at most two in ''G''. Fleischner's theorem states that the square of a finite 2-vertex-connected graph with at least three vertices must always be Hamiltonian. Equivalently, the vertices of every 2-vertex-connected graph ''G'' may be arranged into a cyclic order such that adjacent vertices in this order are at distance at most two from each other in ''G''.
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「Fleischner's theorem」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|